\documentclass[12pt,a4paper,french]{article} \usepackage[francais]{babel} \usepackage[utf8]{inputenc} \usepackage{a4} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{framed} \usepackage{dsfont} \usepackage[amsmath,thmmarks,thref,framed]{ntheorem} \usepackage[dvips]{graphics} \usepackage{epsfig} \usepackage{calc} \usepackage{tabls} \usepackage{slashbox} \usepackage{times} \usepackage{tabularx} \usepackage{multicol} \usepackage{textcomp} \usepackage{pst-all} \usepackage[a4paper]{geometry} \input{symboles.sty} \geometry{hmargin=1cm, vmargin=1.5cm} \title{ Département d'informatique (décembre 09).\\ Partiel de mathématiques discrètes. Semestre 1} \date{} \begin{document} \vspace{-5em} \maketitle \vspace{-5em} \noindent Seule une fiche manuscrite de format A5 est autorisée.\\ \vspace{-3em} \section{QCM} Cette partie contient 60 affirmations. Vous aurez +1 à chaque valeur de vérité trouvée, -1 à chaque erreur (et 0 en absence de réponse). Les notes seront ajustées à l'intervalle $[0;20]$ (les notes négatives auront 0). Q. 1. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite réflexive si, lorsque $x$ est en relation avec $y$, alors $y$ est en relation avec $x$. L'assertion proposée est vraie ou fausse ? %Q. 2. La puissance du continu est la puissance de $\mathds{R}$. %L'assertion proposée est vraie ou fausse ? %Q. 80. Q. 2. Soit $t_1$ et $t_2$ deux termes exprimés dans une algèbre de Boole munie des opérateurs classiques +, . et $\overline{\begin{array}{l}~\end{array}}$. Si $t_1 + t_2 = 1$ alors $t_1 = 1 $ et $t_2$ a une valeur quelconque, et vice versa. L'assertion proposée est vraie ou fausse ? Q. 3. Soit $\mathcal{R}$ une relation binaire. Pour tout $x$ de $E$, il existe au plus un $y$ de $F$ tel que $x \mathcal{R} y$. L'assertion proposée est vraie ou fausse ? Q. 4. Une application est une relation fonctionnelle telle que tout élément de l'ensemble de départ possède au moins une image. L'assertion proposée est vraie ou fausse ? Q. 5. Une application est une relation binaire. L'assertion proposée est vraie ou fausse ? Q. 6. Étant donnée la relation $\mathcal{R}$ dans $C=\{1,2,3,4,5\}$ définie par les points figurant dans le diagramme cartésien: \begin{multicols}{2} \begin{center} \psset{xunit=0.5, yunit=0.5} \begin{pspicture}(0,-0.5)(6,6) %\psgrid \psaxes*[linewidth=1.2pt,labels=all,ticks=all]{->}(0,0)(0,0)(6,6) \savedata{\mydata}[ {{1,2},{1,4},{3,1},{3,4},{3,5},{5,1},{5,2},{5,4}}] \listplot[plotstyle=dots,showpoints=true]{\mydata} \end{pspicture} \end{center} Le domaine de $\mathcal{R}$ est-il $\{1,2,3,4,5\}$? \end{multicols} Q. 7. $\sqrt{} : \mathbb{R}^+ \longrightarrow \mathbb{R}$ est surjective. L'assertion proposée est vraie ou fausse ? Q. 8. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite transitive si $\forall x \in E, x \mathcal{R} x$. L'assertion proposée est vraie ou fausse ? Q. 9. Les relations d'ordre sont les relations réflexive, symétrique et transitive. L'assertion proposée est vraie ou fausse ? Q. 10. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite réflexive lorsque, si $x$ est en relation avec $y$, et si $y$ l'est avec $z$, alors $x$ est en relation avec $z$. L'assertion proposée est vraie ou fausse ? Q. 11. Soit $R$ la relation dans $A=\{1,2,3,4\}$ définie par $R=\{(1,3),(1,4),(3,2),(3,3),(3,4),\}$. A-t-on $R^{-1}=\{(1,3),(1,4),(3,2),(3,3),(3,4),(1,3),(1,4),(3,2),(3,3),(3,4),\}$? Q. 12. Étant donnée la relation $\mathcal{R}$ dans $C=\{1,2,3,4,5\}$ définie par les points figurant dans le diagramme cartésien: \begin{multicols}{2} \begin{center} \psset{xunit=0.5, yunit=0.5} \begin{pspicture}(0,-0.5)(6,6) %\psgrid \psaxes*[linewidth=1.2pt,labels=all,ticks=all]{->}(0,0)(0,0)(6,6) \savedata{\mydata}[ {{1,2},{1,4},{3,1},{3,4},{3,5},{5,1},{5,2},{5,4}}] \listplot[plotstyle=dots,showpoints=true]{\mydata} \end{pspicture} \end{center} Le domaine de $\mathcal{R}$ est-il $\{1,3,5\}$? \end{multicols} Q. 13. Soit $\mathcal{R}$ une relation binaire. $\forall x, x \mathcal{R} x$. L'assertion proposée est vraie ou fausse ? %doublon %Q. 14. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite réflexive si, lorsque $x$ est en relation avec $y$, alors $y$ est en relation avec $x$. L'assertion proposée est vraie ou fausse ? % Q.70. Q. 14. Une application bijective est surjective. L'assertion proposée est vraie ou fausse ? Q. 15. $|$ est une relation d'ordre dans $\mathds{Z}$. L'assertion proposée est vraie ou fausse ? Q. 16. $(\mathds{R},\leqslant)$ est un ensemble ordonné. L'assertion proposée est vraie ou fausse ? Q. 17. Les relations d'ordre sont les relations symétrique, antisymétrique et transitive. L'assertion proposée est vraie ou fausse ? % doublon %Q. 18. Une application est une relation binaire. %L'assertion proposée est vraie ou fausse ? % Q. 64. Q. 18. $\sin : [0,\pi] \longrightarrow [-1,1]$ est surjective. L'assertion proposée est vraie ou fausse ? Q. 19. $(\mathds{N},|)$ est un ensemble ordonné. L'assertion proposée est vraie ou fausse ? Q. 20. $\sin : \mathbb{R} \longrightarrow [-1,1]$ est injective. L'assertion proposée est vraie ou fausse ? Q. 21. $\mathcal{R} = \{ (x,y) \in \mathbb{R}^2, xy = 1 \}$ est une relation fonctionnelle. L'assertion proposée est vraie ou fausse ? Q. 22. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite antisymétrique si $\forall x \in E, (x,x) \in G$. L'assertion proposée est vraie ou fausse ? Q. 23. Dans une algèbre de Boole munie des opérateurs classiques +, . et $\overline{\begin{array}{l}~\end{array}}$, on considère l'expression $E=\overline{a}(a+b)(a+c)(a+d)(a+e)$. La version la plus réduite de $E$ est $\overline{a}bcde$. L'assertion proposée est vraie ou fausse ? Q. 24. $(\mathds{N}^*,|)$ est un ensemble ordonné. L'assertion proposée est vraie ou fausse ? Q. 25. Étant donnée la relation $\mathcal{R}$ dans $C=\{1,2,3,4,5\}$ définie par les points figurant dans le diagramme cartésien: \begin{multicols}{2} \begin{center} \psset{xunit=0.5, yunit=0.5} \begin{pspicture}(0,-0.5)(6,6) %\psgrid \psaxes*[linewidth=1.2pt,labels=all,ticks=all]{->}(0,0)(0,0)(6,6) \savedata{\mydata}[ {{1,2},{1,4},{3,1},{3,4},{3,5},{5,1},{5,2},{5,4}}] \listplot[plotstyle=dots,showpoints=true]{\mydata} \end{pspicture} \end{center} On propose les affirmations suivantes: \begin{enumerate} \item \label{item:af1} $1 \mathcal{R}4$; \item \label{item:af2} $2 \mathcal{R}5$; \item \label{item:af3} $3 \mathcal{R}1$; \item \label{item:af4} $5 \mathcal{R}3$. \end{enumerate} Toutes les relations sont-elles vraies? \end{multicols} Q. 26. Dans une algèbre de Boole munie des opérateurs classiques +, . et $\overline{\begin{array}{l}~\end{array}}$, on considère l'expression $E=\overline{a}(a+b)(a+c)(a+d)(a+e)$. La version la plus réduite de $E$ est 1. L'assertion proposée est vraie ou fausse ? Q. 27. Étant donnée la relation $\mathcal{R}$ dans $C=\{1,2,3,4,5\}$ définie par les points figurant dans le diagramme cartésien: \begin{multicols}{2} \begin{center} \psset{xunit=0.5, yunit=0.5} \begin{pspicture}(0,-0.5)(6,6) %\psgrid \psaxes*[linewidth=1.2pt,labels=all,ticks=all]{->}(0,0)(0,0)(6,6) \savedata{\mydata}[ {{1,2},{1,4},{3,1},{3,4},{3,5},{5,1},{5,2},{5,4}}] \listplot[plotstyle=dots,showpoints=true]{\mydata} \end{pspicture} \end{center} On propose les affirmations suivantes: \begin{enumerate} \item \label{item:af1b} $1 \mathcal{R}4$; \item \label{item:af2b} $2 \mathcal{R}5$; \item \label{item:af3b} $3 \mathcal{R}1$; \item \label{item:af4b} $5 \mathcal{R}3$. \end{enumerate} L'item \ref{item:af4b} est-il toujours faux? \end{multicols} Q. 28. $x \mathcal{R} y \Longleftrightarrow $ \og $x$ et $y$ ont le même reste dans une division par 2 \fg{} est une relation d'ordre sur les entiers strictement positifs. L'assertion proposée est vraie ou fausse ? Q. 29. Une application de $E$ dans $F$ est telle que $\forall x \in E$, il existe un unique élément $y \in F$ en relation avec $x$. L'assertion proposée est vraie ou fausse ? Q. 30. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite réflexive si $\forall x \in E, x \mathcal{R} x$. L'assertion proposée est vraie ou fausse ? Q. 31. $\mathcal{R} = \{ (x,y) \in \mathbb{R}^2, y-x+2 = 0 \}$ est une relation binaire. L'assertion proposée est vraie ou fausse ? %Q. 32. $\mathds{C}$ a la puissance du continu. %L'assertion proposée est vraie ou fausse ?\\ % Q. 79. % doublon %Q. 32. $\sin : \mathbb{R} \longrightarrow [-1,1]$ est injective. %L'assertion proposée est vraie ou fausse ? Q. 32. Les applications bijectives sont les applications injectives et surjectives. L'assertion proposée est vraie ou fausse ? Q. 33. Soit $\mathcal{R}$ une relation binaire. Le graphe de $\mathcal{R}$ est symétrique par rapport à la diagonale. L'assertion proposée est vraie ou fausse ? %Q. 34. La puissance du continu est la puissance de $\mathds{N}$. %L'assertion proposée est vraie ou fausse ? %Q. 78. Q. 34. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite réflexive si la diagonale de $E^2$ est incluse dans $G$. L'assertion proposée est vraie ou fausse ? % doublon %Q. 35. Les relations d'ordre sont les relations réflexive, symétrique et transitive. %L'assertion proposée est vraie ou fausse ? Q. 35. $\subset$ est une relation d'ordre dans $\mathcal{P}(E)$. L'assertion proposée est vraie ou fausse ? Q. 36. Une application injective est une application telle que tout élément de l'ensemble d'arrivée possède au plus un antécédent. L'assertion proposée est vraie ou fausse ? Q. 37. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite transitive lorsque, si $x$ est en relation avec $y$, et si $y$ l'est avec $z$, alors $x$ est en relation avec $z$. L'assertion proposée est vraie ou fausse ? Q. 38. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite transitive si la diagonale de $E^2$ est incluse dans $G$. L'assertion proposée est vraie ou fausse ? Q. 39. Une application surjective est une application telle que tout élément de l'ensemble d'arrivée possède au moins un antécédent. L'assertion proposée est vraie ou fausse ? Q. 40. Étant donnée la relation $\mathcal{R}$ dans $C=\{1,2,3,4,5\}$ définie par les points figurant dans le diagramme cartésien: \begin{multicols}{2} \begin{center} \psset{xunit=0.5, yunit=0.5} \begin{pspicture}(0,-0.5)(6,6) %\psgrid \psaxes*[linewidth=1.2pt,labels=all,ticks=all]{->}(0,0)(0,0)(6,6) \savedata{\mydata}[ {{1,2},{1,4},{3,1},{3,4},{3,5},{5,1},{5,2},{5,4}}] \listplot[plotstyle=dots,showpoints=true]{\mydata} \end{pspicture} \end{center} Le domaine de $\mathcal{R}$ est-il $\{1,3,5\} \times \{1,2,4,5\}$? \end{multicols} Q. 41. $\sin : \mathbb{R} \longrightarrow [-1,1]$ est surjective. L'assertion proposée est vraie ou fausse ? %Q. 42. $\mathds{Z}$ a la puissance du continu. %L'assertion proposée est vraie ou fausse ? %Q. 77. Q. 42. Une application de $F$ dans $E$ est telle que $\forall x \in F$, il existe un unique élément $y \in E$ en relation avec $x$. L'assertion proposée est vraie ou fausse ? Q. 43. Toute application injective est surjective. L'assertion proposée est vraie ou fausse ? Q. 44. On a défini une relation binaire $\mathcal{R}$ entre deux ensembles $E$ et $F$ lorsqu’on s'est donné une partie de $E \times F$. L'assertion proposée est vraie ou fausse ? %Q. 45. $\mathcal{P}\left(\mathds{R}\right)$ a la puissance du continu. %L'assertion proposée est vraie ou fausse ?\\ %Q. 76. %doublon %Q. 45. Soit $\mathcal{R}$ une relation binaire. $\forall x, x \mathcal{R} x$. L'assertion proposée est vraie ou fausse ? % doublon % Q. 45. $\sin : \mathbb{R} \longrightarrow [-1,1]$ est surjective. L'assertion proposée est vraie ou fausse ? Q.45. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite transitive si, lorsque $x$ est en relation avec $y$, alors $y$ ne peut pas être en relation avec $x$ (sauf si $x=y$). L'assertion proposée est vraie ou fausse ? Q. 46. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite transitive quand tout élément est en relation avec lui-même. L'assertion proposée est vraie ou fausse ? Q. 47. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite transitive si, lorsque $x$ est en relation avec $y$, alors $y$ est en relation avec $x$. L'assertion proposée est vraie ou fausse ? Q. 48. \og $x \mathcal{R} y$ si et seulement si $x+y$ est pair \fg{} est une relation d'ordre sur l'ensemble des entiers relatifs. L'assertion proposée est vraie ou fausse ? Q. 49. $\{ (x,y) \in \mathbb{R}^2, |y| = \sqrt{x} \}$ est une relation fonctionnelle. L'assertion proposée est vraie ou fausse ? %Q. 50. $\mathcal{P}\left(\mathds{N}\right)$ a la puissance du continu. %L'assertion proposée est vraie ou fausse ?\\ %Q. 75. Q. 50. $\leqslant$ est une relation d'ordre dans $\mathds{R}$. L'assertion proposée est vraie ou fausse ? Q. 51. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite antisymétrique si $$\forall (x,y,z) \in E^3, (x,y) \in G \textrm{ et } (y,z) \in G \Longrightarrow (x,z) \in G$$. L'assertion proposée est vraie ou fausse ? %Q. 52. $\mathds{D}$ a la puissance du continu. %L'assertion proposée est vraie ou fausse ?\\ %Q. 74. Q. 52. Soit $R$ la relation dans $A=\{1,2,3,4\}$ définie par $R=\{(1,3),(1,4),(3,2),(3,3),(3,4),\}$. A-t-on $R^{-1}=\{(3,1),(4,1),(2,3),(3,3),(4,3)\}$? Q. 53. $(\mathds{Z},|)$ est un ensemble ordonné. L'assertion proposée est vraie ou fausse ? Q. 54. On considère 4 variables booléennes $a$, $b$, $c$ et $d$. Le + est le symbole du OU logique non exclusif, le . est le symbole du ET logique et $\overline{\begin{array}{l}~\end{array}}$ est la négation logique. L'expression $\overline{a} + \overline{b} + c + d $ vaut 1 si et seulement $c.d$ vaut 1. L'assertion proposée est vraie ou fausse ? Q. 55. $|$ est une relation d'ordre dans $\mathds{N}^*$. L'assertion proposée est vraie ou fausse ? Q. 56. On considère 4 variables booléennes $a$, $b$, $c$ et $d$. Le + est le symbole du OU logique non exclusif, le . est le symbole du ET logique et $\overline{\begin{array}{l}~\end{array}}$ est la négation logique. L'égalité $a+b+c+d=0$ est établie si et seulement si $a= b= c= d = 0$. L'assertion proposée est vraie ou fausse ? Q. 57. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite transitive si $$\forall (x,y,z) \in E^3, x \mathcal{R} y \textrm{ et } y \mathcal{R} z \Longrightarrow x \mathcal{R} z$$. L'assertion proposée est vraie ou fausse ? Q. 58. Étant données les fonctions $f:A \rightarrow B$, $g:B \rightarrow C$ et $h:C \rightarrow D$ définies par le diagramme suivants \begin{multicols}{2} \begin{center} \pspicture*(-1,-1)(7,5.4) \scalebox{1}{ \cnodeput*(0,4){a}{a} \cnodeput*(0,3){b}{b} \cnodeput*(0,2){c}{c} \cnodeput*(2,4){1}{1} \cnodeput*(2,3){2}{2} \cnodeput*(2,2){3}{3} \cnodeput*(4,4){x}{x} \cnodeput*(4,3){y}{y} \cnodeput*(4,2){z}{z} \cnodeput*(4,1){w}{w} \cnodeput*(6,4){4}{4} \cnodeput*(6,3){5}{5} \cnodeput*(6,2){6}{6} \rput(-0.2,5.2){$A$} \rput(1.8,5.2){$B$} \rput(3.8,5.2){$C$} \rput(5.8,5.2){$D$} \rput(1,0.5){$f$} \rput(3,0.5){$g$} \rput(5,0.5){$h$} \psellipse(0,3)(0.5,2) \psellipse(2,3)(0.5,2) \psellipse(4,2.5)(0.5,2.5) \psellipse(6,3)(0.5,2) \ncline{->}{a}{2} \ncline{->}{b}{1} \ncline{->}{c}{2} \ncline{->}{2}{x} \ncline{->}{1}{y} \ncline{->}{3}{w} \ncline{->}{x}{4} \ncline{->}{z}{4} \ncline{->}{y}{6} \ncline{->}{w}{5} } \endpspicture \end{center} $f$ est-elle ni injective ni surjective? \end{multicols} %doublon %Q. 59. $(\mathds{N},|)$ est un ensemble ordonné. %L'assertion proposée est vraie ou fausse ? Q.59. Si $f:E \longrightarrow F$ est bijective, alors tout élément de $E$ possède exactement une image dans $F$. L'assertion proposée est vraie ou fausse ? %doublon %Q. 60. $x \mathcal{R} y \Longleftrightarrow $ \og $x$ et $y$ ont le même reste dans une division par 2 \fg{} est une relation d'ordre sur les entiers strictement positifs. %L'assertion proposée est vraie ou fausse ? Q. 60. Une application injective est une application telle que tout élément de l'ensemble d'arrivée possède exactement un antécédent. L'assertion proposée est vraie ou fausse ? % Q. 62. % Q. 63. % Q. 65. % Etant données les fonctions $f:A \rightarrow B$, % $g:B \rightarrow C$ et % $h:C \rightarrow D$ définies par le diagramme suivants % \begin{center} % \pspicture*(-1,-1)(7,5.4) % \scalebox{1}{ % \cnodeput*(0,4){a}{a} % \cnodeput*(0,3){b}{b} % \cnodeput*(0,2){c}{c} % \cnodeput*(2,4){1}{1} % \cnodeput*(2,3){2}{2} % \cnodeput*(2,2){3}{3} % \cnodeput*(4,4){x}{x} % \cnodeput*(4,3){y}{y} % \cnodeput*(4,2){z}{z} % \cnodeput*(4,1){w}{w} % \cnodeput*(6,4){4}{4} % \cnodeput*(6,3){5}{5} % \cnodeput*(6,2){6}{6} % \rput(-0.2,5.2){$A$} % \rput(1.8,5.2){$B$} % \rput(3.8,5.2){$C$} % \rput(5.8,5.2){$D$} % \rput(1,0.5){$f$} % \rput(3,0.5){$g$} % \rput(5,0.5){$h$} % \psellipse(0,3)(0.5,2) % \psellipse(2,3)(0.5,2) % \psellipse(4,2.5)(0.5,2.5) % \psellipse(6,3)(0.5,2) % \ncline{->}{a}{2} % \ncline{->}{b}{1} % \ncline{->}{c}{2} % \ncline{->}{2}{x} % \ncline{->}{1}{y} % \ncline{->}{3}{w} % \ncline{->}{x}{4} % \ncline{->}{z}{4} % \ncline{->}{y}{6} % \ncline{->}{w}{5} % } % \endpspicture % \end{center} % $h \circ g$ est-elle surjective? % Q. 66. Si $f:E \longrightarrow F$ est bijective, alors tout élément de $F$ possède exactement un antécédant dans $E$. L'assertion proposée est vraie ou fausse ? % Q. 67. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite réflexive quand tout élément est en relation avec lui-même. L'assertion proposée est vraie ou fausse ? % Q. 68. Soit $\mathcal{R}$ une relation binaire. Il est possible d'avoir $x \mathcal{R} y$ sans avoir $y \mathcal{R} x$. L'assertion proposée est vraie ou fausse ? % Q. 69. % % % %Q. 72. $\mathds{Q}$ a la puissance du continu. % %L'assertion proposée est vraie ou fausse ?\\ % Q. 72. \begin{large} \begin{center} \begin{tabular}{|l|c|c||l|c|c||l|c|c|} \hline Numéro & V & F & Numéro & V & F & Numéro & V & F \\ \hline Q. 1 & & & Q. 2 & & & Q. 3 & & \\ \hline Q. 4 & & & Q. 5 & & & Q. 6 & & \\ \hline Q. 7 & & & Q. 8 & & & Q. 9 & & \\ \hline Q. 10 & & & Q. 11 & & & Q. 12 & & \\ \hline Q. 13 & & & Q. 14 & & & Q. 15 & & \\ \hline Q. 16 & & & Q. 17 & & & Q. 18 & & \\ \hline Q. 19 & & & Q. 20 & & & Q. 21 & & \\ \hline Q. 22 & & & Q. 23 & & & Q. 24 & & \\ \hline Q. 25 & & & Q. 26 & & & Q. 27 & & \\ \hline Q. 28 & & & Q. 29 & & & Q. 30 & & \\ \hline Q. 31 & & & Q. 32 & & & Q. 33 & & \\ \hline Q. 34 & & & Q. 35 & & & Q. 36 & & \\ \hline Q. 37 & & & Q. 38 & & & Q. 39 & & \\ \hline Q. 40 & & & Q. 41 & & & Q. 42 & & \\ \hline Q. 43 & & & Q. 44 & & & Q. 45 & & \\ \hline Q. 46 & & & Q. 47 & & & Q. 48 & & \\ \hline Q. 49 & & & Q. 50 & & & Q. 51 & & \\ \hline Q. 52 & & & Q. 53 & & & Q. 54 & & \\ \hline Q. 55 & & & Q. 56 & & & Q. 57 & & \\ \hline Q. 58 & & & Q. 59 & & & Q. 60 & & \\ \hline \end{tabular} \end{center} \end{large} \newpage \section{Problèmes} Vous traiterez au choix deux des trois problèmes suivants. \subsection{Une relation d'ordre en algèbre de Boole} Dans une algèbre de Boole munie des opérateurs classiques +, . et $\overline{\begin{array}{l}~\end{array}}$ soit la relation $R$ définie par $$ x R y \Leftrightarrow x +y = y $$ \begin{enumerate} \item A-t-on $a\overline{c}d ~R~ ad$, $ad ~R~ a\overline{c}d$, $a\overline{c}d ~R~ \overline{a}\overline{b}cd$ ? Justifier à chaque fois. \item Montrer que $R$ est une relation d'ordre (réflexive, antisymétrique et transitive). \item La relation est-elle totale? Partielle? Justifier. \end{enumerate} \subsection{Résolution d'équations en algèbre de Boole} On considère une boite noire qui réalise l'addition de deux bits $a$ et $b$ plus une retenu entrante $c_{\textit{in}}$. Elle produit un résultat $s$ et un bit de retenu $c_{\textit{out}}$ en se conformant au tableau suivant: $$ \begin{array}{|c|c|c|c|c|} \hline a &b & c_{\textit{in}} & c_{\textit{out}} & s \\ \hline 0 &0 & 0 &0 & 0 \\ \hline 0 &0 & 1 &0 & 1 \\ \hline 0 &1 & 0 &0 & 1 \\ \hline 0 &1 & 1 &1 & 0 \\ \hline 1 &0 & 0 &0 & 1 \\ \hline 1 &0 & 1 &1 & 0 \\ \hline 1 &1 & 0 &1 & 0 \\ \hline 1 &1 & 0 &1 & 1 \\ \hline \end{array} $$ \begin{enumerate} \item Montrer que la sortie $s$ est $c_{\textit{in}}(\overline{a}.\overline{b} + a.b) + \overline{c_{\textit{in}}}(\overline{a}.b + a.\overline{b})$ \item Montrer que la retenue $c_{\textit{out}}$ de sortie est $a.b + c_{\textit{in}}.a + c_{\textit{in}}.b$ \item Résoudre algébriquement l'équation $s = c_{\textit{out}}$ dont les variables sont $c_{\textit{in}}$, $a$ et $b$. Vérifier la correction des réponses à l'aide du tableau donné ci-dessus. \end{enumerate} \subsection{Les infinis} \begin{enumerate} \item Parmi les ensembles suivants, $\mathbb{N}, \mathbb{Z}, \mathbb{D}, \mathbb{Q}, \mathbb{R}, \mathbb{C}$, lesquels sont dénombrables? Justifier. \item L'ensemble des nombres transcendants est-il dénombrable? Justifier. \item Quelle est la définition d'un ensemble infini? \item Combien y a-t-il d'infinis? Justifier. \item Démontrez que l'intervalle réel [0,1] n'est pas dénombrable. \end{enumerate} \end{document}